package leetcode.tree_problem;

/**
 * @author 一哑7
 * @date 2022/03/17 21:36
 * 剑指 Offer 51. 数组中的逆序对
 * https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 **/
public class 剑指Offer51数组中的逆序对 {
    public int reversePairs(int[] nums) {
        return help(nums , 0 , nums.length - 1);
    }

    private int help(int[] nums, int l, int r) {
        //返回nums的p[l , r]区间中的逆序对个数
        if (l >= r){
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        int left = help(nums , l , mid);
        int right = help(nums , mid + 1 , r);
        if (nums[mid] > nums[mid + 1]){
            //左端比右端大，数组还没有排序好，进行合并
            return merge(nums , l , mid , r) + left + right;
        }
        return left + right;
    }

    private int merge(int[] nums, int l, int mid, int r) {
        //合并数组左右并且返回逆序对个数
        int[] aux = new int[r - l + 1];
        int ret = 0;
        int i = l;
        int j = mid + 1;
        for (int k = 0; k < aux.length; k++) {
            //先把nums数组内容拷贝到新的aux
            aux[k] = nums[i + l];//有可能操作的是后面的数组，
        }
        for (int k = l; k < r; k++) {
            if (i > mid){
                nums[k] = aux[j - l];
                j ++ ;
            }else if (j > r){
                nums[k] = aux[i - l];
                i ++ ;
            }else if (aux[i - l] <= aux[j - l]){
                nums[k] = aux[i - l];
                i ++ ;
            }else {
                //此时左面的数值大于右面，所以有逆序对
                ret += (mid - i) + 1;
                nums[k] = aux[j - l];
                j ++ ;
            }
        }
        return ret;

    }
}

